Husk at et primtal er et heltal $p$ større end $1$ sådan at de eneste faktorer i $p$ er $1$ og $p$ selv.
Nedenfor definerer vi en funktion til at teste om et vilkårligt heltal er et primtal. Hvordan virker funktionen? Hvorfor er det nok at vi ikke tester for alle $i$ mindre end $n$?
In [1]:
def isPrime(n):
if n<2:
return False # et primtal kan ikke være mindre end 2.
for i in range(2,int(n**0.5)+1,1): # vi tester for hvert i mellem 2 og kvadratroden af n om i er divisor af n.
if n%i==0:
return False
return True
Vi kan nu teste om et bestemt tal er et primtal på følgende måde:
In [2]:
print(isPrime(2))
In [3]:
print(isPrime(178143))
In [4]:
print(isPrime(612343237489))
In [5]:
print(isPrime(45912343237124489))
Ville det være muligt at teste primalitet hurtigere end på ovenstående måde? Hvordan kunne vi forbedre vores test?
Der bliver stadig arbejdet på primalitetstest i forskningen i dag. Den første algoritme der var betydeligt hurtigere end metoder ligesom vores ovenpå blev kun udviklet i 1983 og det var kun i 2002 at det blev bevist at problemet kunne løses i polynomiel tid.
Prøv nedenfor at forbedre vores primalitetstest. Hvordan kan vi gøre den hurtigere?
In [6]:
for i in range(2,20,3): # Prøv at forstå hvad der sker i denne for løkke. Kan det måske bruges til at forbedre vores test?
print(i)
In [7]:
def isPrimeImproved(n):
if n<2:
return False
for i in range(2,int(n**0.5)+1,1):
if n%i==0:
return False
return True
Siden primtal er så vigtige ville det være nyttigt hvis vi nemt kunne generere nye primtal. Vi vil nu kigge på funktioner som forhåbentligt kan generere primtal.
Fermat tal er tal af formen $2^{2^n}+1$ for $n$ et naturligt tal. Fermat hævdede i 1650 at alle Fermat tal var primtal. Det tog mere end 80 år for matematikere at afgøre om det var sandt. I skal nu i de næste 2 minutter afgøre om det er sandt.
In [8]:
def fermatNumber(n):
return 2**2**n+1
Prøv i nedenstående celle at ændre på værdien af $k$. Kan i finde et modeksempel?
In [9]:
k=4
print(fermatNumber(k))
print(isPrime(fermatNumber(k)))
Vi prøver nu at teste om udtryk af formen $n^2-n+41$ altid er primtal, hvor $n$ er et naturligt tal.
In [10]:
def possiblePrimeGenerator(n):
return n**2-n+41
In [11]:
n=4;
print(possiblePrimeGenerator(n));
print(isPrime(possiblePrimeGenerator(n)));
In [12]:
for i in range(1,14):
print(possiblePrimeGenerator(i))
print(isPrime(possiblePrimeGenerator(i)));
Det ser ud til at denne funktion i modsætning til Fermat tallene kan bruges til at generere primtal. Tror i det gælder generelt? Kan i begrunde det?
Vi kan repræsentere de 29 bogstaver i det danske alfabet som tal fra 0 til 29 i alfabetisk rækkefølge. Dvs at vi har: a = 0 b = 1 . . . å = 29 Så vil ordet 'datalogi' for eksempel kunne repræsenteres som: 3 0 19 0 11 13 6 8
Cæsar's kodning er et simpelt eksempel på en krypteringstransformation. I Cæsar's kodning adderer vi bare et tal $k$ til de tal der repræsenterer vores ord.
For eksempel kan ordet 'datalogi' repræsenteres som: 3 0 19 0 11 13 6 8
Hvis vi nu adderer 3 til hvert tal får vi tallene: 6 3 22 3 14 16 9 11
svarende til: gdwdoqjl
Det er ikke svært at få vores oprindelige tekst tilbage. Hvad skal vi gøre?
Hvad ville der ske hvis vi i stedet prøvede at addere 12 til hvert tal? Er der noget vi har talt om i dag som kunne bruges for at håndtere problemet?
RSA er et krypteringssystem baseret på offentlige nøgler. Det betyder at jeg for eksempel kan udlevere en offentlig nøgle som fortæller andre hvordan de skal kryptere deres besked til mig sådan at jeg er den eneste der kan dekryptere besked. Modsat Cæsar's kodning er sikkerheden af systemet altså bevaret selvom man ved hvordan krypteringen skal foregå.
Nedenfor ser vi et meget simpelt eksempel på hvordan RSA virker. Nedenstående udregninger kommer nok til at forekomme meget umotiverede. Det er ikke vigtigt at i forstår hvor tallene kommer fra.
Vi vælger først to primtal $p$ og $q$ og finder så deres produkt $n$. Så definerer vi et nyt tal $m$ som er produktet af $p-1$ og $q-1$. Til sidst finder vi så et tal $e$ som er mindre end $m$ og primisk med $m$.
In [13]:
p=61
q=53
n=p*q
m=(p-1)*(q-1)
e=17
De to tal $n=3233$ og $e=17$ udgør nu sammen vores offentlige nøgle og kan bruges til at kryptere en besked. Hvis vi for eksempel vil kryptere bogstavet $w$ repræsenteret ved tallet 22, kan vi udregne:
In [14]:
encryptedMessage = 22**17%n
print(encryptedMessage)
Vores krypterede besked er altså 2558. Det er desværre for så lille en $n$ værdi ikke svært at bryde koden. Vi kan finde den hemmelige del af RSA nøglen som bruges til at dekryptere beskeden meget nemt
In [15]:
for i in range(0,m):
if (i*e%m==1):
print(i)
In [16]:
print(2558**2753%n)
Vi har dermed dekrypteret den oprindelige besked og fået tallet 22 tilbage som repræsenterer bogstavet $w$.
For at undgå at systemet så nemt kan bryges bruges i RSA meget store tal. tallet $n$ beskrevet ovenfor kan for eksempel være af størrelsesorden $10^{120}$. Til sammenligning er $10^{82}$ en øvre grænse for antallet af atomer i det observerbare univers.
I de ovenstående udregninger har vi også valgt en meget dårlig måde at repræsentere vores besked på, ved at betragte hvert bogstav som et tal. Hvorfor er dette problematisk, og hvad kunne man i stedet gøre?
In [16]: